package com.njuaplusplus.www.utils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class Sudoku {

	public class Node {
		public int row, column;
		public Node up, down, left, right;

		public Node() {
			row = column = 0;
			up = down = left = right = this;
		}

	}

	private static final int NumberOfRow = 729;
	private static final int NumberOfColumn = 324;

	private Node[] columnList = new Node[NumberOfColumn];
	private Node[] rowList = new Node[NumberOfRow];
	private Node head = new Node();
	private boolean[] holes = new boolean[81];

	private ArrayList<int[]> solutionList = new ArrayList<int[]>();
	private int[] solution1 = new int[81];

	private int NumberOfSolutionWanted = 1;

	public Sudoku() {
		//		System.out.println("Sudoku()!!!!!!");
		head.column = NumberOfColumn;
		head.row = NumberOfRow;
		Arrays.fill(solution1, -1);
		Arrays.fill(holes, true);
		for (int i=0; i<columnList.length; i++) {
			columnList[i] = new Node();
		}
		for (int i=0; i<rowList.length; i++) {
			rowList[i] = new Node();
		}

		for (int i=0; i<columnList.length; i++) {
			columnList[i].column = i;
			columnList[i].row = 0;
			columnList[i].left = head;
			columnList[i].right = head.right;
			head.right = columnList[i];
			columnList[i].right.left = columnList[i];
		}

		//		for (Node node=columnList[0].right; node!=columnList[0]; node=node.right) {
		//			System.out.println("column == " + node.column + " row == " + node.row);
		//		}

		for (int i=0; i<rowList.length; i++) {
			rowList[i].row = i;
			rowList[i].column = 0;
			rowList[i].up = head;
			rowList[i].down = head.down;
			head.down = rowList[i];
			rowList[i].down.up = rowList[i];
		}

	}


	public void initSudokuMatrix(String strSudoku) {
		if (strSudoku.length() == 81) {
			for (int i=0; i<rowList.length; i++) {
				int r = i / 9 / 9 % 9;
				//				System.out.println("r == " + r);
				int c = i / 9 % 9;
				//				System.out.println("c == " + c);
				int val = i % 9 + 1;
				//				System.out.println("val == " + val);
				if (strSudoku.charAt(r*9+c) == '.' || strSudoku.charAt(r*9+c) == (char)(val+'0') ) {
					linkRowAndColum(i, r*9+val-1);
					//					System.out.println("81+c*9+val-1 == " + (81+c*9+val-1));
					linkRowAndColum(i, 81+c*9+val-1);
					int tr = r / 3;
					int tc = c / 3;
					linkRowAndColum(i, 162+(tr*3+tc)*9+val-1);
					linkRowAndColum(i, 243+r*9+c);
				}
			}

			for (int i=0; i<rowList.length; i++) {
				rowList[i].left.right = rowList[i].right;
				rowList[i].right.left = rowList[i].left;
			}
		}
	}
	
	public void initSudokuMatrix(int[] aSudoku) {
		
		if (aSudoku.length == 81) {
			String strSudoku = "";
			for (int item : aSudoku) {
				if (item < 0) {
					strSudoku += ".";
				}
				else {
					strSudoku += item;
				}
			}
			System.out.println("initSudokuMatrix by int[] str length == " + strSudoku.length());
			System.out.println("strSudoku == " + strSudoku);
			initSudokuMatrix(strSudoku);
			
		}
	}

	private void linkRowAndColum(int row, int column) {
		columnList[column].row++;
		Node newNode = new Node();
		newNode.row = row;
		newNode.column = column;
		newNode.left = rowList[row];
		newNode.right = rowList[row].right;
		rowList[row].right = newNode;
		newNode.right.left = newNode;
		newNode.up = columnList[column];
		newNode.down = columnList[column].down;
		columnList[column].down = newNode;
		newNode.down.up = newNode;

	}

	private void removeRowByColumn(int column) {
		columnList[column].right.left = columnList[column].left;
		columnList[column].left.right = columnList[column].right;
		for (Node t=columnList[column].down; t!=columnList[column]; t=t.down) {
			for (Node tt=t.right; tt!=t; tt=tt.right) {
				columnList[tt.column].row--;
				tt.up.down = tt.down;
				tt.down.up = tt.up;
			}
			t.left.right = t.right;
			t.right.left = t.left;
		}
	}

	private void resumeRowbyColumn(int column) {
		for (Node t=columnList[column].down; t!=columnList[column]; t=t.down) {
			t.right.left = t;
			t.left.right = t;
			for (Node tt=t.left; tt!=t; tt=tt.left) {
				columnList[tt.column].row++;
				tt.down.up = tt;
				tt.up.down = tt;
			}
		}
		columnList[column].left.right = columnList[column];
		columnList[column].right.left = columnList[column];
	}

	private void printSolution(int[] m) {
		int[] ans = new int[81];
		for (int i : m) {
			int t = i / 9 % 81;
			int val = i % 9 + 1;
			ans[t] = val;
		}

		for (int i=0; i<ans.length; i++) {
			System.out.print(ans[i] + " ");
			if ((i+1)%9 == 0)
				System.out.println();
		}
	}

	private void solveSudoku(int k) {
		if (head.right==head) {
			solutionList.add(solution1);
			return;
		}
		Node t, tt;
		int tc=head.right.column, min=head.right.row;
		for (t=head.right.right; t!=head; t=t.right) {
			if (columnList[t.column].row < min) {
				min = columnList[t.column].row;
				tc = t.column;
				if (min <= 1)
					break;
			}
		}
		removeRowByColumn(tc);
		for (t=columnList[tc].down; t!=columnList[tc]; t=t.down) {
			solution1[k] = t.row;
			t.left.right = t;
			for (tt=t.right; tt!=t; tt=tt.right) {
				removeRowByColumn(tt.column);
			}
			t.left.right = t.right;
			solveSudoku(k+1);
			if (solutionList.size() >= NumberOfSolutionWanted)
				return;
			t.right.left = t;
			for (tt=t.left; tt!=t; tt=tt.left) {
				resumeRowbyColumn(tt.column);
			}
			t.right.left = t.left;
		}
		resumeRowbyColumn(tc);
	}

	public void solveSudoku() {
		solveSudoku(0);
		for (int i=0; i<solutionList.size(); i++) {
			printSolution(solutionList.get(i));
			System.out.println("\n");
		}
	}

	public void printSudokuMatix() {
		for (int i=0; i<columnList.length; i++) {
			for (Node node=columnList[i].down; node!=columnList[i]; node=node.down) {
				System.out.print("row == " + node.row + " column == " + node.column);
			}
			System.out.println();
		}
	}
	
	public int[] generateSudoku(int space) {
		
		cleanSolutionList();
		
		Arrays.fill(holes, false);
		Random r = new Random();
//		initSudokuMatrix(".................................................................................");
		int[] initarray = new int[81];
		Arrays.fill(initarray, -1);
		
		for(int i=0; i<9; i++) {
			int random = r.nextInt(81);
			while (initarray[random] > 0) {
				random = r.nextInt(81);
			}
			initarray[random] = i + 1;
		}
		
		System.out.println("The init Array:");
		for (int i : initarray) {
			System.out.print(i + " ");
		}
		System.out.println();
		
		initSudokuMatrix(initarray);
		
		
		solveSudoku();
		 
		
		for(int i=0; i<space; i++) {
			int random = r.nextInt(81);
			while (holes[random]) {
				random = r.nextInt(81);
			}
			
			holes[random] = true;
		}
		int[] ans = new int[81];
		for (int i=0; i<solution1.length; i++) {
			int t = solution1[i] / 9 % 81;
			int val = solution1[i] % 9 + 1;
			if (holes[t]) {
				ans[t] = -1;
			}
			else {
				ans[t] = val;
			}
		}
		return ans;
	}

	public ArrayList<int[]> getResultList() {
		if (solutionList.size() < 1) {
			solveSudoku();
			if (solutionList.size() < 1) {
				return null;
			}
		}
		ArrayList<int[]> result = new ArrayList<int[]>();
		for (int i=0; i<solutionList.size(); i++) {
			int[] ans = new int[81];
			int[] m = solutionList.get(i);
			for (int j : m) {
				int t = j / 9 % 81;
				int val = j % 9 + 1;
				ans[t] = val;
			}
			
			result.add(ans);

		}
		return result;
	}

	public boolean[] getHoles() {
		return holes;
	}
	
	public boolean isHoles(int index) {
		return holes[index];
	}
	
	public boolean isCorrect(int position, int[] aSudoku) {
		return isColumnCorrect(position, aSudoku) && isRowCorrect(position, aSudoku) && isCellCorrect(position, aSudoku);
	}
	
	public boolean isCorrect(int[] aSudoku) {
		return isColumnCorrect(aSudoku) && isRowCorrect(aSudoku) && isCellCorrect(aSudoku);
	}
	
	private boolean isColumnCorrect(int[] aSudoku) {
		
		return false;
	}
	
	private boolean isColumnCorrect(int position, int[] aSudoku) {
		int column = position % 9;
		boolean[] isFound = new boolean[9];
		Arrays.fill(isFound, false);
		for (int i=0; i<9; i++) {
			int number = aSudoku[column + i * 9] - 1;
			System.out.println("Test Column number == " + number);
			if (number < 0) {
				continue;
			}
			if (!isFound[number]) {
				isFound[number] = true;
			}
			else {
				System.out.println("Wrong column == " + column);
				return false;
			}
		}
		return true;
	}
	
	private boolean isRowCorrect(int[] aSudoku) {
		return false;
	}
	
	private boolean isRowCorrect(int position, int[] aSudoku) {
		int row = position / 9;
		boolean[] isFound = new boolean[9];
		Arrays.fill(isFound, false);
		for (int i=0; i<9; i++) {
			int number = aSudoku[row * 9 + i] - 1;
			System.out.println("Test Row number == " + number);
			if (number < 0) {
				continue;
			}
			if (!isFound[number]) {
				isFound[number] = true;
			}
			else {
				System.out.println("Wrong row == " + row);
				return false;
			}
		}
		return true;
	}
	
	private boolean isCellCorrect(int[] aSudoku) {
		
		return false;
	}
	
	private boolean isCellCorrect(int position, int[] aSudoku) {
		int row = position / 9;
		int column = position % 9;
		
		int topLeftRowNumber= row / 3;
		int topLeftColumnNumber = column / 3;
		boolean[] isFound = new boolean[9];
		Arrays.fill(isFound, false);
		for (int i=0; i<3; i++) {
			for (int j=0; j<3; j++) {
				int number = aSudoku[(topLeftRowNumber * 3 + i) * 9 + topLeftColumnNumber * 3 + j] - 1;
				System.out.println("Test Cell number == " + number);
				if (number < 0) {
					continue;
				}
				if (!isFound[number]) {
					isFound[number] = true;
				}
				else {
					System.out.println("Wrong cell == " + ((topLeftRowNumber/3) + (topLeftColumnNumber/3)));
					return false;
				}
			}
		}
		return true;
	}
	
	public void cleanSolutionList() {
		solutionList.clear();
		System.out.println("SolutionList is cleared, isempty() == " + solutionList.isEmpty());
	}

}
